1. Field
The present disclosure relates to computer systems and methods in which data resources are shared among data consumers while preserving data integrity and consistency relative to each consumer. More particularly, the invention concerns the use of transactional memory for memory reference operations.
2. Description of the Prior Art
By way of background, transactional memory allows a system to execute a group of memory-reference operations as if they ran atomically with respect to other transactions in that same system. Recently, hardware transactional memory implementations have started appearing, but all of these enforce limits on transaction memory footprint, which is the set of memory locations that the transaction has read from or written to. These limits are determined by hardware resources such as cache size, store-buffer entries, and TLB entries. Unfortunately, these hardware implementations are not generally able to distinguish between memory private to a given CPU (such as stack, per-CPU variables, thread-local storage, and so on) and memory shared among CPUs (such as global variables and heap storage). One reason that hardware implementations are not able to make this sort of distinction is that there are exceptions, for example, a given CPU might publish a pointer to some of its on-stack data, which would mean that such data would need to be tracked if used in a transaction.
The foregoing limitation is especially troublesome for transactions that need to manipulate a large quantity of private data, for example, when initializing a large block of shared memory that is being published by the transaction. If the memory block is large enough, the hardware transaction will have an unnecessarily high probability of failure.
One way to avoid this problem is to allow transactions to be suspended. Any changes to memory made while a transaction is suspended do not count against the transaction's memory footprint. After the non-transactional operation has completed, the transaction may be resumed, and this transaction might subsequently succeed or fail. Transaction suspension may also be used to implement thread-level speculation, in which suspension is used to communicate state from one iteration to the next.
FIGS. 1 and 2 illustrate the difference between a normal and a suspended transaction. In both figures, time advances from left to right and the program stack grows in the upward direction. In both figures, there is a function foo( ) that invokes a library function txbegin( ) to start a transaction. This library function returns, at which point foo( ) invokes a function bar( ). In a normal transaction (FIG. 1), bar( )'s memory footprint must remain small in order to avoid aborting the transaction due to cache overflow. In contrast, a suspended transaction (FIG. 2) can have a much larger memory footprint because memory references during suspended mode do not count against any limits to the transaction's footprint. In both cases, bar( ) returns to foo( ), which then invokes the library function txcommit( ) to commit the transaction.
However, the code that runs while the transaction is suspended must be careful to avoid writing to any memory that is within the transaction's memory footprint. If the suspended-mode code overwrites any locations within the transaction's memory footprint, the transaction may be unable to properly roll back the contents of those locations upon a subsequent abort. This eventuality is equivalent to data corruption, and must thus be avoided. This problem is illustrated in FIG. 3. The sequence of calls is the same as before, except that bar( ), running in transaction suspend mode, overwrites the memory locations previously used by txbegin( )'s stack frame. This negates the ability of the transactional-memory hardware to restore state to txbegin( ), resulting in garbage as shown in the upper right.
In contrast, a normal transaction does not suffer from this problem. As shown in FIG. 4, because bar( ) overwrites txbegin( )'s stack frame in transactional mode, the txabort( ) can restore txbegin( )'s stack frame, allowing state to be rolled back to before the transaction started.
The inability to handle suspended-mode overwriting interferes with abstraction. To see this, consider the situation shown in the figures, where transaction entry and exit are implemented using library functions that use the stack, writing data onto the stack that is overwritten by the calling function. As shown in FIG. 4, this is not a problem when the calling function is still executing transactionally, so the stack locations will be restored should the transaction abort. But as shown in FIG. 3, this safety net does not apply while the transaction is suspended, which means that if the suspended code performs a function call that overlays the portion of stack used by the transaction-enter library function, a later transaction abort will corrupt the stack.
The present disclosure proposes a mechanism that permits suspending transactions without risk of data corruption upon a subsequent transaction abort.